package src.dp.entire_bag;

import java.util.HashSet;
import java.util.List;

public class no139 {//单词拆分

    /**
     * 1. dp数组下标含义：单词就是物品，字符串s就是背包，单词能否组成字符串s，即这些物品能否刚好把背包装满
     * dp[i]: 字符串长度为 i，能被单词组成，dp[i]就为 true
     * 2. 递推公式：if( [j,i] && dp[j]=true )  dp[i]=true;
     * 3. 初始化数组：dp[0]=true
     * 4. 遍历顺序：有顺序，所以先背包后物品
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;

        //遍历背包，留一个i=0位置表示空串，因为字符串非空所以从 i=1 遍历，即表示从第一个字母开始遍历
        for (int i = 1; i <= s.length(); i++) {
            for (String word : wordDict) {  //遍历物品
                int len = word.length();
                //substring方法分区间是左闭右开 [ )
                if (i >= len && dp[i - len] && s.substring(i - len, i).equals(word)) {
                    dp[i] = true;
                    break;  //匹配到一个单词后立马退出这轮循环，让 i 后移找下一个单词
                }
            }
        }
        return dp[s.length()];

    }

    //方法2：用一个set存单词
    public boolean wordBreak2(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i && !dp[i]; j++) {
                if (set.contains(s.substring(j, i)) && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }

}
